1545. Можете ли Вы это решить?

Давайте посмотрим на приведенную ниже картинку. На ней изображены точки в декартовой системе координат. Между точками можно передвигаться только по направлениям, которые указаны стрелками. Для того чтобы попасть из начальной точки в конечную необходимо совершить количество шагов, равное числу промежуточных пройденных точек + 1. Например, на пути из (0, 3) в (3, 0) необходимо пройти промежуточные точки (1, 2) и (2, 1). Количество шагов равно 2 + 1 = 3. В этой задаче Вам следует подсчитать количество шагов, необходимое для попадания из одной точки в другую. Двигаться в обратном направлении к направлению стрелок запрещено.

Вход. Первая строка содержит количество тестов n (0 < n ≤ 500). Далее следует n строк, каждая из которых содержит четыре целых числа (0 ≤ каждое число ≤ 100000). Первая пара чисел задает координаты начальной точки, вторая пара задает координаты конечной точки. Координаты задаются в виде (x, y).

Выход. Для каждого теста в отдельной строке следует вывести его номер и количество шагов, необходимое для того чтобы добраться из начальной точки в конечную. Считайте, что такой путь всегда существует.

Пример входа	Пример выхода
3 0 0 0 1 0 0 1 0 0 0 0 2	Case 1: 1 Case 2: 2 Case 3: 3

РЕШЕНИЕ

сетки

Анализ алгоритма

Вычислим количество перемещений, которое следует совершить для попадания по стрелкам из точки (0, 0) в точку (x, y). Движение происходит по диагоналям. Для попадания на первую диагональ, соединяющую точки (0, 1) и (1, 0), достаточно совершить одно перемещение из (0, 0) в (0, 1). Для попадания во вторую диагональ, соединяющую точки (0, 2) и (2, 0), из начала первой диагонали (точки (0, 1)), необходимо совершить два перемещения. И так далее: для попадания в k - ую диагональ, соединяющую точки (0, k) и (k, 0), из начала (k – 1) - ой диагонали (точки (0, k – 1)), необходимо совершить k перемещений.

Точка (x, y) находится на диагонали номер x + y. Для достижения этой диагонали следует совершить 1 + 2 + ... + (x + y – 1) + (x + y) = (1 + x + y) * (x + y) / 2 = (x + y) * (x + y + 1) / 2 шагов. Попав за это количество шагов в точку (0, x + y), еще следует пройти x шагов чтобы попасть в точку (x, y). Таким образом, число перемещений из (0, 0) в (x, y) равно dist(x, y) = (x + y) * (x + y + 1) / 2 + x.

Чтобы попасть из точки (x₁, y₁) в точку (x₂, y₂) следует совершить dist(x₂, y₂) – dist(x₁, y₁) перемещений.

Пример

Рассмотрим третий тест. Чтобы попасть из точки (0, 0) в точку (0, 2) следует пройти точки (0, 1), (1, 0), сделав при этом 3 перемещения:

dist(0, 2) = (0 + 2) * (0 + 2 + 1) / 2 + 0 = 3

Реализация алгоритма

Функция вычисления числа перемещений от точки (0, 0) до (x, y) имеет вид:

int dist(int x, int y)

{

return (1+x+y) * (x+y) / 2 + x;

}

Обрабатываем последовательно тесты. Для каждой входной пары точек (x₁, y₁) и (x₂, y₂) вычисляем и выводим значение dist(x₂, y₂) – dist(x₁, y₁).

scanf("%d",&n);

for(i = 0; i < n; i++)

{

scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

res = dist(x2,y2) - dist(x1,y1);

printf("Case %d: %d\n",i+1,res);

}